ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Tree alignment</title>

</head>

Tree alignment

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Computational_phylogenetics" title="Computational phylogenetics">computational phylogenetics</a>, tree alignment is a <a href="Computational_problem" title="Computational problem">computational problem</a> concerned with producing <a href="Multiple_sequence_alignment" title="Multiple sequence alignment">multiple sequence alignments</a>, or alignments of three or more sequences of <a href="DNA" title="DNA">DNA</a>, <a href="RNA" title="RNA">RNA</a>, or <a href="Protein" title="Protein">protein</a>. Sequences are arranged into a <a href="Phylogenetic_tree" title="Phylogenetic tree">phylogenetic tree</a>, modeling the evolutionary relationships between <a href="Species" title="Species">species</a> or <a href="Taxa" class="mw-redirect" title="Taxa">taxa</a>. The <a href="Edit_distance" title="Edit distance">edit distances</a> between sequences are calculated for each of the tree's internal vertices, such that the sum of all edit distances within the tree is minimized. Tree alignment can be accomplished using one of several algorithms with various trade-offs between manageable tree size and computational effort.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

Input: A set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> of sequences, a <a href="Phylogenetic_tree" title="Phylogenetic tree">phylogenetic tree</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> leaf-labeled by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> and an <a href="Edit_distance" title="Edit distance">edit distance</a> function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> between sequences.

Output: A labeling of the internal vertices of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma _{e\in T}d(e)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{e\in T}d(e)}</annotation>

</semantics>

</math><img src="./301dfeb5fad725e4842d04a9163f17faac14ffb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.038ex; height:2.843ex;" alt="{\displaystyle \Sigma _{e\in T}d(e)}" loading="lazy"> is minimized, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d(e)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d(e)}</annotation>

</semantics>

</math><img src="./50f789b00e727e164f808a01ea98631c70c747eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.109ex; height:2.843ex;" alt="{\displaystyle d(e)}" loading="lazy"> is the <a href="Edit_distance" title="Edit distance">edit distance</a> between the endpoints of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e}</annotation>

</semantics>

</math><img src="./cd253103f0876afc68ebead27a5aa9867d927467.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle e}" loading="lazy">.

The task is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Background">Background</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Sequence_alignment">Sequence alignment</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Sequence_alignment" title="Sequence alignment">Sequence alignment</a></div>

In <a href="Bioinformatics" title="Bioinformatics">bioinformatics</a>, the basic method of information processing is to contrast the sequence data. <a href="Biologist" title="Biologist">Biologists</a> use it to discover the function, structure, and evolutionary information in biological sequences. The following analyses are based on the <a href="Sequence_assembly" title="Sequence assembly">sequence assembly</a>: the <a href="Phylogenetic" class="mw-redirect" title="Phylogenetic">phylogenetic</a> analysis, the <a href="Haplotype" title="Haplotype">haplotype</a> comparison, and the prediction of <a href="RNA" title="RNA">RNA</a> structure. Therefore, the efficiency of sequence alignment will directly affect the efficacy of solving these problems. In order to design a rational and efficient sequence alignment, the algorithm derivation becomes an important branch of research in the field of bioinformatics.

Generally, sequence alignment means constructing a string from two or more given strings with the greatest similarity by adding letters, deleting letters, or adding a space for each <a href="Connection_string" title="Connection string">string</a>. The multiple sequence alignment problem is generally based on pairwise sequence alignment and currently, for a pairwise sequence alignment problem, biologists can use a <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> approach to obtain its optimal solution. However, the multiple sequence alignment problem is still one of the more challenging problems in bioinformatics. This is because finding the optimal solution for multiple sequence alignment has been proven as an <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a> problem and only an approximate optimal solution can be obtained.<a href="#cite_note-2">[2]</a>

<div class="mw-heading mw-heading3"><h3 id="Distance_matrix_method">Distance matrix method</h3></div>

Distance method measures the minimum operation number of character <a href="Insertion_(genetics)" title="Insertion (genetics)">insertions</a>, <a href="Deletion_(genetics)" title="Deletion (genetics)">deletions</a>, and <a href="Base-pair_substitution" class="mw-redirect" title="Base-pair substitution">substitutions</a> that are required to transform one sequence u to the other sequence v when being operated on a pair of strings. The calculation of edit distance can be based on <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>, and the equation is in O(|u|×|v|) time, where |u| and |v| are the lengths of u and v.<a href="#cite_note-3">[3]</a> The efficient estimation of edit distance is essential as Distance method is a basic principle in <a href="Computational_biology" title="Computational biology">computational biology</a><a href="#cite_note-4">[4]</a> For functions of hereditary properties "symmetrization" can be used. Due to a series of functions being used to calculate edit distance, different functions may result in different results. Finding an optimal edit distance function is essential for the tree alignment problem.

<div class="mw-heading mw-heading2"><h2 id="The_problem_of_tree_alignment">The problem of tree alignment</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

Tree alignment results in a <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> problem, where scoring modes and alphabet sizes are restricted. It can be found as an algorithm, which is used to find the optimized solution. However, there is an exponential relationship between its efficiency and the number sequences, which means that when the length of the sequence is very large, the computation time required to get results is enormously long. Using star alignment to get the approximate optimized solution is faster than using tree alignment. However, whatever the degree of multiple-sequence similarity is, the time complexity of star alignment has a proportional relationship with the square of the sequence number and the square of the sequence average length. As usual, the sequence in MSA is so long that it is also inefficient or even unacceptable. Therefore, the challenge of reducing the time complexity to linear is one of the core issues in tree alignment.

<div class="mw-heading mw-heading2"><h2 id="Combinatorial_optimization_strategy">Combinatorial optimization strategy</h2></div>

<a href="Combinatorial_optimization" title="Combinatorial optimization">Combinatorial optimization</a> is a good strategy to solve MSA problems. The idea of combinatorial optimization strategy is to transform the multiple sequence alignment into pair sequence alignment to solve this problem. Depending on its transformation strategy, the combinatorial optimization strategy can be divided into the tree alignment algorithm and the star alignment algorithm. For a given multi-sequence set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> ={<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{1}}</annotation>

</semantics>

</math><img src="./eb8baad278d51283e0ef3c99898d583cf2c8a8fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.145ex; height:2.009ex;" alt="{\displaystyle s_{1}}" loading="lazy">,...,<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s_{n}}</annotation>

</semantics>

</math><img src="./d671890050b21484dde3087d000700c97fc3b03c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.309ex; height:2.009ex;" alt="{\displaystyle s_{n}}" loading="lazy"> }, find an <a href="Evolutionary_tree" class="mw-redirect" title="Evolutionary tree">evolutionary tree</a> which has n leaf nodes and establishing one to one relationship between this evolutionary tree and the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy">. By assigning the sequence to the internal nodes of the evolutionary tree, we calculate the total score of each edge, and the sum of all edges' scores is the score of the evolutionary tree. The aim of tree alignment is to find an assigned sequence, which can obtain a maximum score, and get the final matching result from the evolutionary tree and its nodes' assigned sequence. Star alignment can be seen as a special case of the tree alignment. When we use star alignment, the evolutionary tree has only one internal node and n leaf nodes. The sequence, which is assigned to the internal node, is called the core sequence.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading3"><h3 id="The_keyword_tree_theory_and_the_Aho-Corasick_search_algorithm">The keyword tree theory and the Aho-Corasick search algorithm</h3></div>

When the <a href="Combinatorial_game_theory" title="Combinatorial game theory">combinatorial</a> optimization strategy is used to transform the multiple sequence alignment into pair sequence alignment, the main problem is changed from "How to improve the efficiency of multiple sequence alignment" to "How to improve the efficiency of pairwise sequence alignment." The Keyword Tree Theory and the Aho-Corasick search algorithm is an efficient approach to solve the pairwise sequence alignment problem. The aim of combining the keyword tree theory and the Aho-Corasick search algorithm is to solve this kind of problem: for a given long string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> and a set of short strings <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">={<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy">,<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{2}}</annotation>

</semantics>

</math><img src="./43f1b08d7d69712872e051c2b33fdfa9f5d42319.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{2}}" loading="lazy">,... ,<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{z}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{z}}</annotation>

</semantics>

</math><img src="./1dbd3c1a6173a7974e0095301da94447c5f67657.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.261ex; height:2.009ex;" alt="{\displaystyle p_{z}}" loading="lazy">} (z∈N,z>1), find the location of all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy">. The keyword tree produced by set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> is used, and then searched for in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> with this keyword tree through the Aho-Corasick search algorithm.<a href="#cite_note-6">[6]</a> The total time complexity of using this method to find all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy">'s location in the T is O(<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">+<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">+<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">), where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">=|<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy">| (the length of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy">), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">=Σ|<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy">| (the sum of all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy">'s lengths) and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> means the sum of occurrence for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy">.

<div class="mw-heading mw-heading4"><h4 id="Keyword_tree_theory">Keyword tree theory</h4></div>

The keyword tree of the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">={<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy">,<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{2}}</annotation>

</semantics>

</math><img src="./43f1b08d7d69712872e051c2b33fdfa9f5d42319.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{2}}" loading="lazy">,... ,<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{z}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{z}}</annotation>

</semantics>

</math><img src="./1dbd3c1a6173a7974e0095301da94447c5f67657.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.261ex; height:2.009ex;" alt="{\displaystyle p_{z}}" loading="lazy"> } (z∈N,z>1) is a rooted tree, whose root denoted by K, and this keyword tree satisfies:

(1): Each edge clearly demarcates one letter.

(2): Any two edges separated from the same node are to correspond to different letters.

(3) Each pattern <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy"> (i=1,2,...,z) corresponds to a node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, and the path from the root K to the node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> can exactly correctly spell the string <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy">.

For each leaf node of this K tree, it corresponds to one of the certain patterns of set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">.

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(v)}</annotation>

</semantics>

</math><img src="./06dc417764e6a058b0b5d4f69917ed41382b5f98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.52ex; height:2.843ex;" alt="{\displaystyle L(v)}" loading="lazy"> is used to represent the STRING which is connected from the root node to the node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Lp(v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Lp(v)}</annotation>

</semantics>

</math><img src="./136155dd61f60f3b293240d2a67d3237f67514f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.689ex; height:2.843ex;" alt="{\displaystyle Lp(v)}" loading="lazy"> will then be used to represent the length of the longest suffix (also, this suffix is the prefix of one of patterns in the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">). Searching this prefix from the root node in the keyword tree, and the last node denoted by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{v}}</annotation>

</semantics>

</math><img src="./a5449610d28f85fb4d2ccebbfa7d3daf87e3f3b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.424ex; height:2.009ex;" alt="{\displaystyle n_{v}}" loading="lazy"> when the search is over.<a href="#cite_note-7">[7]</a>

For example, the set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy">={potato, tattoo, theater, other}, and the keyword tree is shown on the right. In that example, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(v)}</annotation>

</semantics>

</math><img src="./06dc417764e6a058b0b5d4f69917ed41382b5f98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.52ex; height:2.843ex;" alt="{\displaystyle L(v)}" loading="lazy">=potat, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Lp(v)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Lp(v)}</annotation>

</semantics>

</math><img src="./136155dd61f60f3b293240d2a67d3237f67514f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.689ex; height:2.843ex;" alt="{\displaystyle Lp(v)}" loading="lazy">=|tat|=3, and the failure link of the node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> is shown in that figure.

Establishing a failure link is the key to improve the time complexity of the Aho-Corasick algorithm. It can be used to reduce the original polynomial time to the linear time for searching. Therefore, the core of keyword tree theory is to find all failure links (which also means finding all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{v}}</annotation>

</semantics>

</math><img src="./a5449610d28f85fb4d2ccebbfa7d3daf87e3f3b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.424ex; height:2.009ex;" alt="{\displaystyle n_{v}}" loading="lazy">s) of a keyword tree in the linear time. It is assumed that every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{v}}</annotation>

</semantics>

</math><img src="./a5449610d28f85fb4d2ccebbfa7d3daf87e3f3b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.424ex; height:2.009ex;" alt="{\displaystyle n_{v}}" loading="lazy"> of all nodes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy">, whose distance from the root node is less than or equal <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, can be found. The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{v}}</annotation>

</semantics>

</math><img src="./a5449610d28f85fb4d2ccebbfa7d3daf87e3f3b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.424ex; height:2.009ex;" alt="{\displaystyle n_{v}}" loading="lazy"> of the node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> whose distance from the root node is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> + 1 can then be sought for. Its parent node is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v'}</annotation>

</semantics>

</math><img src="./19f1c5b0af1f30c41cb8bc0ba3bfea98681da268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.812ex; height:2.509ex;" alt="{\displaystyle v'}" loading="lazy">, and the letter represented by the node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math><img src="./e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v'}</annotation>

</semantics>

</math><img src="./19f1c5b0af1f30c41cb8bc0ba3bfea98681da268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.812ex; height:2.509ex;" alt="{\displaystyle v'}" loading="lazy">, is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">.

(1): If the next letter of the node <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{v}'}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{v}'}</annotation>

</semantics>

</math><img src="./83c293b23c2146abf783934926f4ea959a7139ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.424ex; height:2.509ex;" alt="{\displaystyle n_{v}'}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">, the other node of this edge can be set as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{v}}</annotation>

</semantics>

</math><img src="./a5449610d28f85fb4d2ccebbfa7d3daf87e3f3b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.424ex; height:2.009ex;" alt="{\displaystyle n_{v}}" loading="lazy">=<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">.

(2): If all letters are not <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> by searching all edges between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{v}'}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{v}'}</annotation>

</semantics>

</math><img src="./83c293b23c2146abf783934926f4ea959a7139ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.424ex; height:2.509ex;" alt="{\displaystyle n_{v}'}" loading="lazy"> and its child nodes, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(n_{v})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(n_{v})}</annotation>

</semantics>

</math><img src="./7dc5cd74949d11fe44f543f64d6f5fced5eacc4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.816ex; height:2.843ex;" alt="{\displaystyle L(n_{v})}" loading="lazy"> is a suffix of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(n_{v}')}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(n_{v}')}</annotation>

</semantics>

</math><img src="./af6c4aa886f6594eeda13e4b20e5a0ce4a040c21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.816ex; height:2.843ex;" alt="{\displaystyle L(n_{v}')}" loading="lazy"> plus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. Because this suffix matches the STRING beginning with the root node (similar to prefix), the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> after <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{v}'}">

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{v}'}</annotation>

</semantics>

</math><img src="./83c293b23c2146abf783934926f4ea959a7139ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.424ex; height:2.509ex;" alt="{\displaystyle n_{v}'}" loading="lazy"> can be detected or not. If not, this process can be continued until <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> or the root node is found.

<div class="mw-heading mw-heading4"><h4 id="Aho-Corasick_search_algorithm">Aho-Corasick search algorithm</h4></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Aho%E2%80%93Corasick_string_matching_algorithm" class="mw-redirect" title="Aho–Corasick string matching algorithm">Aho–Corasick string matching algorithm</a></div>

After establishing all failure links in the keyword tree, the Aho-Corasick search algorithm is used to find the locations of all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{i}}</annotation>

</semantics>

</math><img src="./3ba1396129f7be3c7f828a571b6649e6807d10d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.292ex; height:2.509ex;" alt="{\displaystyle P_{i}}" loading="lazy"> (i=1,2,...,z) in the linear time. In this step, the time complexity is O(m+k).

<div class="mw-heading mw-heading2"><h2 id="Other_strategies">Other strategies</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Multiple_sequence_alignment" title="Multiple sequence alignment">Multiple sequence alignment</a></div>

In MSA, DNA, RNA, and proteins, sequences are usually generated and they are assumed to have an evolutionary relationship. By comparing generated maps of RNA, DNA, and sequences from evolutionary families, people can assess conservation of proteins and find functional gene domains by comparing differences between evolutionary sequences. Generally, heuristic algorithms and tree alignment graphs are also adopted to solve multiple sequence alignment problems.

<div class="mw-heading mw-heading3"><h3 id="Heuristic_algorithm">Heuristic algorithm</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Heuristic_(computer_science)" title="Heuristic (computer science)">Heuristic (computer science)</a></div>

Generally, <a href="Heuristic_algorithm" class="mw-redirect" title="Heuristic algorithm">heuristic algorithms</a> rely on the <a href="Iterative" class="mw-redirect" title="Iterative">iterative</a> strategy, which is to say that based on a comparison method, optimizing the results of multiple sequence alignment by the iterative process. Davie M. proposed using the <a href="Particle_swarm_optimization" title="Particle swarm optimization">particle swarm optimization</a> algorithm to solve the multiple sequence alignment problem; Ikeda Takahiro proposed a heuristic algorithm which is based on the <a href="A*_search_algorithm" title="A* search algorithm">A* search algorithm</a>; E. Birney first proposed using the <a href="Hidden_Markov_model" title="Hidden Markov model">hidden Markov model</a> to solve the multiple sequence alignment problem; and many other biologists use the <a href="Genetic_algorithm" title="Genetic algorithm">genetic algorithm</a> to solve it.<a href="#cite_note-8">[8]</a><a href="#cite_note-9">[9]</a> All these algorithms generally are robust and insensitive to the number of sequences, but they also have shortcomings. For example, the results from the particle swarm optimization algorithm are unstable and its merits depend on the selection of random numbers, the runtime of the A* search algorithm is too long, and the genetic algorithm is easy to fall into local excellent.

<div class="mw-heading mw-heading3"><h3 id="Tree_alignment_graph">Tree alignment graph</h3></div>

Roughly, tree alignment graph aims to align trees into a graph and finally synthesize them to develop statistics. In biology, tree alignment graphs (TAGs) are used to remove the evolutionary conflicts or overlapping taxa from sets of trees and can then be queried to explore uncertainty and conflict. By integrating methods of aligning, synthesizing and analyzing, the TAG aims to solve the conflicting relationships and partial overlapping <a href="Taxon" title="Taxon">taxon</a> sets obtained from a wide range of sequences. Also, the tree alignment graph serves as a fundamental approach for <a href="Supertree" title="Supertree">supertree</a> and <a href="Grafting" title="Grafting">grafting</a> exercises, which have been successfully tested to construct supertrees by Berry.<a href="#cite_note-10">[10]</a> Because the transformation from trees to a graph contain similar <a href="Node_(graph_theory)" class="mw-redirect" title="Node (graph theory)">nodes</a> and <a href="Glossary_of_graph_theory#Basics" title="Glossary of graph theory">edges</a> from their source trees, TAGs can also provide extraction of original source trees for further analysis. TAG is a combination of a set of aligning trees. It can store conflicting hypotheses evolutionary relationship and synthesize the source trees to develop evolutionary hypotheses. Therefore, it is a basic method to solve other alignment problems.<a href="#cite_note-11">[11]</a>

<ul><li><a href="Generalized_tree_alignment" title="Generalized tree alignment">Generalized tree alignment</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 20em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFElias2006" class="citation cs2">Elias, Isaac (2006), "Settling the intractability of multiple alignment", J Comput Biol, 13 (7): 1323–1339, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.256">10.1.1.6.256</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1089%2Fcmb.2006.13.1323">10.1089/cmb.2006.13.1323</a>, <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/17037961">17037961</a></cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> L Wang, T Jiang. On the complexity of multiple sequence alignment[J]. Journal of Computational Biology, 194,1(4):337— 34.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> Yen Hung Chen, On the bottleneck tree alignment problems, INFORMATION SCIENCES; JUN 1, 2010; 180; 11; p2134-p2141

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFOstrovskyRabani2007" class="citation journal cs1">Ostrovsky, Rafail; Rabani, Yuval (2007-10-01). "Low distortion embeddings for edit distance". Journal of the ACM. 54 (5). Association for Computing Machinery (ACM): 23–es. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1284320.1284322">10.1145/1284320.1284322</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15341956">15341956</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Serafim Batzoglou. The many faces of sequence alignment[J]. Briefings in Bioinformatics. <a rel="nofollow" class="external text" href="http://bib.oxfordjournals.org/content/6/1/6.full.pdf+html">2005,6(1):6—22</a>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> Aho A V, Corasick M J. Efficient string matching: an aid to bibliographic search[J]. Communications of ACM, <a rel="nofollow" class="external text" href="ftp://163.13.200.222/assistant/bearhero/prog/%A8%E4%A5%A6/ac_bm.pdf">1975,18(6): 333—340</a>.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> D Gusfield. Algorithms on strings, trees and sequences: computer science and computational biology[M]. <a rel="nofollow" class="external text" href="http://www.cambridge.org/us/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/algorithms-strings-trees-and-sequences-computer-science-and-computational-biology">Cambridge: Cambridge University Press.1997.</a>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> RobertC Edgar, Serafim Batzoglou. Multiple sequence alignment[J]. Current Opinion in Structural Biology. <a rel="nofollow" class="external text" href="http://robotics.stanford.edu/~serafim/Publications/2006_MSA_COSB.pdf">2006,16(3):368— 373</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131023062245/http://robotics.stanford.edu/~serafim/Publications/2006_MSA_COSB.pdf">Archived</a> 2013-10-23 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> Notredame C, Higgins D.G. SAGA:sequence alignment by genetic algorithm [J]. Nucleic Acids Research. <a rel="nofollow" class="external text" href="http://www.tcoffee.org/Publications/Ps_pdf/saga_paper.pdf">1996,24(8):1515-1524</a>.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> Wilkinson M, Pisani D, Measuring support and finding unsupported relationships in supertrees, Systematic Biology 54:823-831.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> Stephen A. Smith, Joseph W. Brown, analyzing and synthesizing phylogenies using tree alignment graphs, PLoS Computational Biology 9(9).

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-27" href="https://en.wikipedia.org/wiki/?title=Tree_alignment&oldid=1292504328">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>